package tree.test236;

import listbyorder.utils.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/16 9:05
 */
public class Solution1 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q) return root;

        HashMap<TreeNode, TreeNode> map = new HashMap<>();   // 存储每个节点父节点的位置
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        map.put(root, null);     // 根节点的父节点为null
        while (!map.containsKey(p) || !map.containsKey(q)) {
            root = stack.pop();
            if (root.left != null) {
                stack.push(root.left);
                map.put(root.left, root);
            }
            if (root.right != null) {
                stack.push(root.right);
                map.put(root.right, root);
            }
        }
        HashSet<TreeNode> path = new HashSet<>();
        // 倒着还原 p 的路径，并将每个节点加入到 set 中
        while (p != null) {
            path.add(p);
            p = map.get(p);
        }

        // 倒着遍历 q 的路径，判断是否在 p 的路径中
        while (q != null) {
            if (path.contains(q)) {
                break;
            }
            q = map.get(q);
        }
        return q;
    }
}
